package pagedisplace

import (
	"fmt"
	"math"
	"math/rand"
	"strconv"
	"time"
)

// 页面结构体
type Page struct {
	PageNumber int
}

// 常量
const (
	FIFO = "先进先出算法"
	LRU  = "最近最久未使用算法"
)

var (
	// lru算法页面列表
	lruPageList []Page
	// 页面列表
	PageList []Page
	// 页面访问队列
	PageQueue []Page
	// 内存块
	Memory []Page
	// 内存块数量
	MemoryNum int
	// 缺页次数
	MissPageNum int
	// 置换次数
	DisplaceNum int
)

// 初始化随机的页面列表，LRU页面列表，页面访问队列
func Create(pageNum int, pageAccessNum int, memoryNum int) {
	MemoryNum = memoryNum
	PageList = make([]Page, pageNum)
	for i := 1; i <= pageNum; i++ {
		page := Page{
			PageNumber: i,
		}
		PageList[i-1] = page
	}
	lruPageList = PageList
	PageQueue = make([]Page, pageAccessNum)
	rand.Seed(time.Now().UnixNano())
	for i := 0; i < len(PageQueue); i++ {
		randNum := rand.Intn(pageNum) + 1
		for j := 0; j < len(PageList); j++ {
			if randNum == PageList[j].PageNumber {
				PageQueue[i] = PageList[j]
				break
			}
		}
	}
}

// 显示页面置换算法结果
func ShowPageDisplace(displaceAlgorithmName ...string) {
	fmt.Printf("页号列表：")
	for i := 0; i < len(PageList); i++ {
		fmt.Printf("%v\t", PageList[i])
	}
	fmt.Println()
	fmt.Printf("内存块数：%v\n", MemoryNum)
	fmt.Printf("页访问序列：")
	for i := 0; i < len(PageQueue); i++ {
		fmt.Printf("%v\t", PageQueue[i])
	}
	fmt.Println()
	// 计算缺页率（小数点后两位）
	value, _ := strconv.ParseFloat(fmt.Sprintf("%.2f", float64(MissPageNum)/float64(len(PageQueue))), 64)
	value = math.Ceil(value * 100)

	for i := 0; i < len(displaceAlgorithmName); i++ {
		if displaceAlgorithmName[i] == FIFO {
			fmt.Printf("使用%v一共产生了%v次缺页，缺页率为：%v%%，并进行了%v次页置换。\n", FIFO, MissPageNum, value, DisplaceNum)
		}
		if displaceAlgorithmName[i] == LRU {
			fmt.Printf("使用%v一共产生了%v次缺页，缺页率为：%v%%，并进行了%v次页置换。\n", LRU, MissPageNum, value, DisplaceNum)
		}
	}
}

// 判断是否在内存块中
func IsInMemory(page Page) bool {
	for i := 0; i < len(Memory); i++ {
		if Memory[i] == page {
			return true
		}
	}
	return false
}

// 删除列表中的某个元素
func DeletePageElement(list []Page, page Page) (result []Page) {
	for _, v := range list {
		if v != page {
			result = append(result, v)
		}
	}
	return result
}

// FIFO算法
func FifoAlgorthm() {
	// 将页面添加到内存块中
	for i := 0; i < len(PageQueue); i++ {
		if !IsInMemory(PageQueue[i]) {
			// 尾插法，先来的在第一
			Memory = append(Memory, PageQueue[i])
			MissPageNum++
		}
		if len(Memory) == MemoryNum {
			break
		}
	}
	// 判断是否在内存块中，如果不在就把内存块的第一个元素去除并在末尾添加页面
	for i := 0; i < len(PageQueue); i++ {
		if !IsInMemory(PageQueue[i]) {
			Memory = Memory[1:]
			Memory = append(Memory, PageQueue[i])
			MissPageNum++
			DisplaceNum++
		}
	}
}

// LRU算法（通过维护LRU页面列表来判断哪个页面是最久未使用的）
func LruAlgorthm() {
	flag := 0
	// 将页面添加到内存块中
	for i := 0; i < len(PageQueue); i++ {
		if !IsInMemory(PageQueue[i]) {
			Memory = append(Memory, PageQueue[i])
			if flag == 0 {
				// 将LRU页面列表的第一个元素替换为第一个添加到内存块中的元素
				for j := 0; j < len(lruPageList); j++ {
					if PageQueue[i] == lruPageList[j] {
						// 交换元素位置
						tmp := lruPageList[0]
						lruPageList[0] = lruPageList[j]
						lruPageList[j] = tmp
						flag = 1
					}
				}
			}
			MissPageNum++
		}
		if len(Memory) == MemoryNum {
			break
		}
	}
	// 判断是否在内存块中，如果不在就判断内存块中某个页面是否在LRU页面列表第一位，如果是就把该元素从内存块中剔除，然后将LRU页面列表第一个元素添加到末尾并将第一个元素剔除
	for i := 0; i < len(PageQueue); i++ {
		if !IsInMemory(PageQueue[i]) {
			for j := 0; j < len(Memory); j++ {
				if Memory[j] == lruPageList[0] {
					Memory = DeletePageElement(Memory, Memory[j])
					lruPageList = append(lruPageList, lruPageList[0])
					lruPageList = lruPageList[1:]
				}
			}
			Memory = append(Memory, PageQueue[i])
			DisplaceNum++
			MissPageNum++
		}
	}
}
